import random


def conflict(state, next_x):
    """
    判断新位置是否冲突
    :param state: 已存在的皇后的位置（索引表示第几行，值表示第几列）
    :param next_x: 下一个皇后的水平位置（列）
    :return: 是否冲突
    """
    next_y = len(state)         # 下一个皇后的垂直位置（行）
    for i in range(next_y):     # 考察每个皇后是否与next_x冲突
        if abs(state[i] - next_x) in (0, next_y - i):
            # state[i] - next_x == 0 # 与第i个皇后在同一列
            # abs(state[i] - next_x) == next_y - i
            # 与第i个皇后的水平距离和垂直距离相等（位于一条对角线上）
            return True
    return False


def queens(num=8, state=()):
    """
    给定最后皇后的位置
    :param num: 皇后总数
    :param state: 已放好皇后的位置
    :return: 返回不会引发冲突的位置
    """
    for pos in range(num):
        if not conflict(state, pos):
            if len(state) == num - 1:
                yield (pos,)
            else:
                for result in queens(num, state + (pos,)):
                    yield (pos,) + result


def prettyprint(solution):

    def line(_pos, length=len(solution)):
        return '. ' * _pos + 'X ' + '. ' * (length - _pos - 1)

    for pos in solution:
        print(line(pos))


x = list(queens(3))
print(x)

x = list(queens(4))
print(x)

for sol in queens(8):
    print(sol)
    print("\n")

print(len(list(queens(8))))

prettyprint(random.choice(list(queens(8))))
